home *** CD-ROM | disk | FTP | other *** search
/ Mac Mania 2 / MacMania 2.toast / Demo's / Tools&Utilities / Programming / Programmers' Challenge / SwapBlocks.c < prev   
Encoding:
C/C++ Source or Header  |  1994-04-12  |  11.5 KB  |  375 lines  |  [TEXT/KAHL]
  1. /* SwapBlocks ---------------------------------------------
  2.  *
  3.  * Response to Apr 94 MacTech Programmer's Challenge.
  4.  *
  5.  * Object:
  6.  * Exchange contents of two adjacent memory blocks.
  7.  *
  8.  * Redirection:
  9.  * This is an interesting problem, but what would make
  10.  * this guy really useful? As stated, the blocks for
  11.  * the challenge are 4i bytes long and start on 4j
  12.  * aligned addresses. These are special circumstances
  13.  * which apply to Memory Manager blocks, and then, only
  14.  * on 68020 or later cpu's. Memory blocks on the 68000
  15.  * are merely even aligned and even length. Further,
  16.  * this could be a word processor tool for swapping runs
  17.  * of bytes, but we would have to relax the alignment
  18.  * and size restrictions even further to arbitrary address
  19.  * and length since we would almost always be pointing
  20.  * to characters interior to a handle.
  21.  *
  22.  * I have written the routine to give its best
  23.  * performance, subject to a specified minimum enforced
  24.  * alignment and atom size (smallest unit to move).
  25.  * This is controlled at compile time by:
  26.  *
  27.  * typedef long  Atom, for len = 4i,  addr = 4j,
  28.  * typedef short Atom, for len = 2i,  addr = 2j,
  29.  * typedef Byte  Atom, for len = any, addr = any.
  30.  *
  31.  * Note- due to an ancient law of portability, preprocessor
  32.  * directives are not allowed to compare enums, types,
  33.  * sizeof()s or anything else that has machine dependency
  34.  * hidden in it. This means you have to #define the
  35.  * AtomSize manually. This is needed to select the proper
  36.  * performance crossover points for that type.
  37.  *
  38.  * But wait there's more...
  39.  * You might not tolerate a 644 byte dedicated word
  40.  * swapper in your text editor, but a 96 byte one
  41.  * might fit. We handle that.
  42.  *
  43.  * You can tailor the routine to your requirements
  44.  * for execution speed vs. code size by setting the
  45.  * JobMode constant according to table:
  46.  *
  47.  * JobMode   Buffers  MonsterCopies  MonsterSwaps
  48.  * ----------------------------------------------
  49.  * Smallest |   No         No             No
  50.  * Small    |   No         No            Yes
  51.  * Fast     |  Yes         No            Yes
  52.  * Fastest  |  Yes        Yes            Yes
  53.  *
  54.  * billKarsh
  55.  *
  56.  */
  57.  
  58. #pragma options( honor_register, !assign_registers )
  59.  
  60. /* ---------------------------------------------------- */
  61. #define    Smallest                0
  62. #define    Small                   1
  63. #define    Fast                    2
  64. #define    Fastest                 3
  65. /* ---------------------------------------------------- */
  66.  
  67. /* ---------------------------- */
  68. /*  User Selectable Parameters
  69. /* ---------------------------- */
  70.  
  71. #define    JobMode                 Fastest
  72. #define    Verify_p1_LowerThan_p2  0
  73.  
  74. /* Sorry, you must #define your chosen Atom's size by
  75.    hand. The preprocessor won't accept sizeof operators.
  76.    Yuck! The XOvers below vary according to this size,
  77.    so we have to know it.
  78. */
  79.  
  80. typedef long                    Atom;
  81. #define    AtomSize                4
  82.  
  83. /* ---------------------------------------------------- */
  84. #if JobMode >= Fast
  85. #    define    UseBuffer           1
  86. #endif
  87. #if JobMode == Fastest
  88. #    define MonsterCopy          1
  89. #endif
  90. #if JobMode >= Small
  91. #    define MonsterSwap          1
  92. #endif
  93. /* ---------------------------------------------------- */
  94. #define    Lo3B                    0x00ffffff
  95. /* ---------------------------------------------------- */
  96. #if AtomSize == 4
  97. #    define    FwdXOver            144
  98. #    define    BckXOver            120
  99. #    define    SwpXOver            44
  100. #elif AtomSize == 2
  101. #    define    FwdXOver            48
  102. #    define    BckXOver            44
  103. #    define    SwpXOver            32
  104. #else
  105. #    define    FwdXOver            24
  106. #    define    BckXOver            20
  107. #    define    SwpXOver            12
  108. #endif
  109. /* ---------------------------------------------------- */
  110. #define    FwdOp                                          \
  111.     *dst++ = *src++
  112. /* ---------------------------------------------------- */
  113. #define    BckOp                                          \
  114.     *--pR = *--pL
  115. /* ---------------------------------------------------- */
  116. #define    SwpOp                                          \
  117.     q     = *pL;                                       \
  118.     *pL++ = *pR;                                       \
  119.     *pR++ = q
  120. /* ---------------------------------------------------- */
  121. #define    Cases3_1( op )                                 \
  122.     case 3:     op;                                    \
  123.     case 2:     op;                                    \
  124.     case 1:     op
  125. /* ---------------------------------------------------- */
  126. #define    Cases7_1( op )                                 \
  127.     case 7:     op;                                    \
  128.     case 6:     op;                                    \
  129.     case 5:     op;                                    \
  130.     case 4:     op;                                    \
  131.     Cases3_1( op )
  132. /* ---------------------------------------------------- */
  133. #define    CalcPasses( bits )                             \
  134.     nS /= sizeof(Atom);                                \
  135.     q = nS & ((1 << bits) - 1);                        \
  136.     nS >>= bits;                                       \
  137.     ++nS
  138. /* ---------------------------------------------------- */
  139. #define    Monster( op, cases )                           \
  140.     switch( (short)q ) {                               \
  141.         case 0:                                        \
  142.             while( --nS ) {                            \
  143.                 op;                                    \
  144.                 cases( op );                           \
  145.             }                                          \
  146.     }
  147. /* ---------------------------------------------------- */
  148. #if MonsterCopy == 1
  149. #define    CopyInc( dst, src, n )                         \
  150.     nS = n;                                            \
  151.     if( nS > FwdXOver ) {                              \
  152.         _CopyInc(                                      \
  153.          (Atom*)(dst), (Atom*)(src), nS );             \
  154.     }                                                  \
  155.     else {                                             \
  156.         pL = (Atom*)(dst);                             \
  157.         pR = (Atom*)(src);                             \
  158.         do { *pL++ = *pR++; } while(nS-=sizeof(Atom)); \
  159.     }
  160. #else
  161. #define    CopyInc( dst, src, n )                         \
  162.     nS = n;                                            \
  163.     pL = (Atom*)(dst);                                 \
  164.     pR = (Atom*)(src);                                 \
  165.     do { *pL++ = *pR++; } while(nS-=sizeof(Atom))
  166. #endif
  167. /* ---------------------------------------------------- */
  168. #if MonsterCopy == 1
  169. #define    CopyDec( dst, src, n )                         \
  170.     nS = n;                                            \
  171.     pR = (Atom*)((Byte*)(dst) + nS);                   \
  172.     pL = (Atom*)((Byte*)(src) + nS);                   \
  173.     if( nS > BckXOver ) {                              \
  174.         CalcPasses( 2 );                               \
  175.         Monster( BckOp, Cases3_1 );                    \
  176.     }                                                  \
  177.     else {                                             \
  178.         do { BckOp; } while(nS-=sizeof(Atom));         \
  179.     }
  180. #else
  181. #define    CopyDec( dst, src, n )                         \
  182.     nS = n;                                            \
  183.     pR = (Atom*)((Byte*)(dst) + nS);                   \
  184.     pL = (Atom*)((Byte*)(src) + nS);                   \
  185.     do { BckOp; } while(nS-=sizeof(Atom))
  186. #endif
  187. /* ---------------------------------------------------- */
  188. #if MonsterSwap == 1
  189. #define    Swap                                           \
  190.     if( nS > SwpXOver ) {                              \
  191.         CalcPasses( 3 );                               \
  192.         Monster( SwpOp, Cases7_1 );                    \
  193.     }                                                  \
  194.     else {                                             \
  195.         do { SwpOp; } while(nS-=sizeof(Atom));         \
  196.     }
  197. #else
  198. #define    Swap                                           \
  199.     do { SwpOp; } while(nS-=sizeof(Atom))
  200. #endif
  201. /* ---------------------------------------------------- */
  202. #define MacroMania              true
  203. /* ---------------------------------------------------- */
  204.  
  205. #if JobMode == Fastest
  206. /* _CopyInc -----------------------------------------------
  207.  *
  208.  * Copy specified number of Bytes from src to dst.
  209.  *
  210.  * Addresses are incremented, so src and dst can overlap
  211.  * iff dst <= src.
  212.  *
  213.  */
  214.  
  215. static void _CopyInc(
  216.     register Atom           *dst,
  217.     register const Atom     *src,
  218.     register unsigned long  nS )
  219. {
  220.     short    q, pad;
  221.     
  222.     CalcPasses( 3 );
  223.     Monster( FwdOp, Cases7_1 );
  224. }
  225. #endif
  226.  
  227. /* SwapBlocks ---------------------------------------------
  228.  *
  229.  */
  230.  
  231. void SwapBlocks(
  232.     void           *p1,
  233.     void           *p2,
  234.     void           *swapPtr,
  235.     unsigned long  size1,
  236.     unsigned long  size2,
  237.     unsigned long  swapSize )
  238. {
  239.     register Atom   *pL, *pR, *p0;
  240.     register long   nL, nR, nS, q;
  241.     Boolean         done;
  242.     short           pad;
  243.     
  244.     if( !(nL = size1) || !(nR = size2) ) return;
  245.     
  246.     p0 = p1;
  247.  
  248. /* --------------------------------------------------------
  249.     If you can safely assume that p1 is always lower
  250.     or same as p2, define Verify_p1_LowerThan_p2 = 0.
  251.     (the #if section is not necessary).
  252.     
  253.     If "1" and "2" are simply labels, indicating
  254.     nothing about position in memory of the blocks,
  255.     then you must order them by activating the #if
  256.     section. Define Verify_p1_LowerThan_p2 = 1.
  257.     
  258.     Ordering means comparing addresses, which treats
  259.     them as 32-bit numbers, NO MATTER the current cpu
  260.     addressing mode. If GetMMUMode returns true, we
  261.     are in 32-bit mode - all 32-bits are significant.
  262.     
  263.     In 24-bit mode, when the cpu uses an address to
  264.     load or store something, it totally ignores the
  265.     high-byte of the address. The high-byte may be
  266.     random garbage. In this mode we suppress any
  267.     garbage before comparing by masking it to zero.
  268. */
  269.  
  270. #if Verify_p1_LowerThan_p2 == 1
  271.  
  272.     pR = p2;
  273.     
  274.     if( !GetMMUMode() ) {
  275.         p0 = (Atom*)((long)p0 & Lo3B);
  276.         pR = (Atom*)((long)pR & Lo3B);
  277.     }
  278.     
  279.     if( pR < p0 ) {
  280.         q  = (long)p0;
  281.         p0 = pR;
  282.         p2 = (Atom*)q;
  283.         
  284.         q  = nL;
  285.         nL = nR;
  286.         nR = q;
  287.     }
  288. #endif
  289. /* ----------------------------------------------------- */
  290.  
  291. /* ----------- */
  292. /*   Buffer?   */
  293. /* ----------- */
  294.  
  295. /*    First, make use of buffer if can. This is faster in
  296.     most cases. A notable exception is equal size case
  297.     which is best done in situ (let drop through).
  298.     
  299.     Compare only the smaller size with buffer. If left
  300.     is smaller, we can use post-increment addressing
  301.     which is the faster mode. If right is smaller,
  302.     use pre-decrement mode. We omit seeing if
  303.     right-smaller will work with post-increment mode
  304.     (if left also fits buffer).    Preflighting overhead
  305.     swallows us up very quickly.
  306. */
  307.  
  308. #if UseBuffer == 1
  309.  
  310.     if( nL < nR ) {
  311.         if( nL <= swapSize ) {
  312.             CopyInc( swapPtr, p0, nL );
  313.             CopyInc( p0, p2, nR );
  314.             CopyInc( (Byte*)p0 + nR, swapPtr, nL );
  315.             return;
  316.         }
  317.     }
  318.     else if( nL > nR ) {
  319.         if( nR <= swapSize ) {
  320.             CopyInc( swapPtr, p2, nR );
  321.             CopyDec( (Byte*)p0 + nR, p0, nL );
  322.             CopyInc( p0, swapPtr, nR );
  323.             return;
  324.         }
  325.     }
  326. #endif
  327.  
  328. /* ----------- */
  329. /*   In Situ   */
  330. /* ----------- */
  331.  
  332. /*    This algorithm always does the job, buffer or not.
  333.  
  334.     Find the smaller block. Swap it immediately into
  335.     its final place. Now the larger block is in two
  336.     out-of-order, but contiguous pieces. Wait a minute,
  337.     this is what we started with! The only differences
  338.     are: now the sizes are {smaller, larger - smaller},
  339.     and the start addresses have to keep up with the
  340.     new pieces.
  341.     
  342.     We repeat until the two pieces were the same length.
  343.     In other words, the final swap didn't break anybody
  344.     in two. This can end with sizes larger than Atom-Atom.
  345.     It depends on whether the smaller evenly divides the
  346.     larger.
  347. */
  348.  
  349.     done = false;
  350.  
  351.     do {
  352.     
  353.         pL = p0;
  354.         pR = p2;
  355.  
  356.         if( nL < nR ) {
  357.             nR = nR - nL;
  358.             pR = (Atom*)((Byte*)pR + nR);
  359.             nS = nL;
  360.         }
  361.         else if( nL > nR ) {
  362.             p0 = (Atom*)((Byte*)pL + nR);
  363.             nL = nL - nR;
  364.             nS = nR;
  365.         }
  366.         else {
  367.             nS = nL;
  368.             done = true;
  369.         }
  370.         
  371.         Swap;
  372.         
  373.     } while( !done );
  374. }
  375.